package oneday.y2021.m10;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MajorityElementii_229 {

    public List<Integer> majorityElement(int[] nums) {
        int cand1 = Integer.MIN_VALUE;
        int cand2 = Integer.MIN_VALUE;
        int cnt1 = 0;
        int cnt2 = 0;
        for (int num : nums) {
            if (cand1 == num) {
                cnt1++;
            } else if (cand2 == num) {
                cnt2++;
            } else if (cnt1 == 0) {
                cand1 = num;
                cnt1++;
            } else if (cnt2 == 0) {
                cand2 = num;
                cnt2++;
            } else {
                cnt1--;
                cnt2--;
            }
        }

        cnt1 = cnt2 = 0;
        for (int num : nums) {
            if (num == cand1) {
                cnt1++;
            } else if (num == cand2) {
                cnt2++;
            }
        }

        List<Integer> ans = new ArrayList<>();
        if (cnt1 > nums.length / 3) ans.add(cand1);
        if (cnt2 > nums.length / 3) ans.add(cand2);
        return ans;
    }
}
/**
 * public class oneday.y2021.m10.MajorityElementii_229 {
 *   public oneday.y2021.m10.MajorityElementii_229();
 *     Code:
 *        0: aload_0
 *        1: invokespecial #1                  // Method java/lang/Object."<init>":()V
 *        4: return
 *
 *   public java.util.List<java.lang.Integer> majorityElement(int[]);
 *     Code:
 *        0: ldc           #3                  // int -2147483648
 *        2: istore_2
 *        3: ldc           #3                  // int -2147483648
 *        5: istore_3
 *        6: iconst_0
 *        7: istore        4
 *        9: iconst_0
 *       10: istore        5
 *       12: aload_1
 *       13: astore        6
 *       15: aload         6
 *       17: arraylength
 *       18: istore        7
 *       20: iconst_0
 *       21: istore        8
 *       23: iload         8
 *       25: iload         7
 *       27: if_icmpge     101
 *       30: aload         6
 *       32: iload         8
 *       34: iaload
 *       35: istore        9
 *       37: iload_2
 *       38: iload         9
 *       40: if_icmpne     49
 *       43: iinc          4, 1
 *       46: goto          95
 *       49: iload_3
 *       50: iload         9
 *       52: if_icmpne     61
 *       55: iinc          5, 1
 *       58: goto          95
 *       61: iload         4
 *       63: ifne          75
 *       66: iload         9
 *       68: istore_2
 *       69: iinc          4, 1
 *       72: goto          95
 *       75: iload         5
 *       77: ifne          89
 *       80: iload         9
 *       82: istore_3
 *       83: iinc          5, 1
 *       86: goto          95
 *       89: iinc          4, -1
 *       92: iinc          5, -1
 *       95: iinc          8, 1
 *       98: goto          23
 *      101: iconst_0
 *      102: dup
 *      103: istore        5
 *      105: istore        4
 *      107: aload_1
 *      108: astore        6
 *      110: aload         6
 *      112: arraylength
 *      113: istore        7
 *      115: iconst_0
 *      116: istore        8
 *      118: iload         8
 *      120: iload         7
 *      122: if_icmpge     159
 *      125: aload         6
 *      127: iload         8
 *      129: iaload
 *      130: istore        9
 *      132: iload         9
 *      134: iload_2
 *      135: if_icmpne     144
 *      138: iinc          4, 1
 *      141: goto          153
 *      144: iload         9
 *      146: iload_3
 *      147: if_icmpne     153
 *      150: iinc          5, 1
 *      153: iinc          8, 1
 *      156: goto          118
 *      159: new           #4                  // class java/util/ArrayList
 *      162: dup
 *      163: invokespecial #5                  // Method java/util/ArrayList."<init>":()V
 *      166: astore        6
 *      168: iload         4
 *      170: aload_1
 *      171: arraylength
 *      172: iconst_3
 *      173: idiv
 *      174: if_icmple     189
 *      177: aload         6
 *      179: iload_2
 *      180: invokestatic  #6                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
 *      183: invokeinterface #7,  2            // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
 *      188: pop
 *      189: iload         5
 *      191: aload_1
 *      192: arraylength
 *      193: iconst_3
 *      194: idiv
 *      195: if_icmple     210
 *      198: aload         6
 *      200: iload_3
 *      201: invokestatic  #6                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
 *      204: invokeinterface #7,  2            // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
 *      209: pop
 *      210: aload         6
 *      212: areturn
 * }
 */